{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Computing the Z-Normalized Euclidean Distance from Dot Products\n",
    "\n",
    "In the [Matrix Profile I](https://www.cs.ucr.edu/~eamonn/STOMP_GPU_final_submission_camera_ready.pdf) and [Matrix Profile II](https://www.cs.ucr.edu/~eamonn/PID4481997_extend_Matrix%20Profile_I.pdf) papers, the Z-normalized Euclidean distance between a query subsequence, $Q_{i,m}=(q_i, q_{i+1}, q_{i+2}\\ldots, q_{i+m-1})$, and the $i^{th}$ subsequence, $T_{i,m}=(t_i, t_{i+1}, t_{i+2}, \\ldots, t_{i+m-1})$, with window size, $m$, in the time series, $T$, can be computed following:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align}\n",
    "    D(Q_{i,m}, T_{i,m}) ={}&\n",
    "        \\sqrt{\n",
    "            \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                \\left(\n",
    "                    \\frac{t_{i+j}-M_{T_{i,m}}}{\\Sigma_{T_{i,m}}}\n",
    "                    - \n",
    "                    \\frac{q_{i+j}-\\mu_{Q_{i,m}}}{\\sigma_{Q_{i,m}}}\n",
    "                \\right)^2\n",
    "        }\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\sqrt{\n",
    "            \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                \\left[\n",
    "                    \\left(\n",
    "                        \\frac{t_{i+j}-M_{T_{i,m}}}{\\Sigma_{T_{i,m}}}\n",
    "                    \\right)\n",
    "                    -\n",
    "                    2\n",
    "                    \\left(\n",
    "                        \\frac{t_{i+j}-M_{T_{i,m}}}{\\Sigma_{T_{i,m}}}\n",
    "                    \\right)\n",
    "                    \\left(\n",
    "                        \\frac{q_{i+j}-\\mu_{Q_{i,m}}}{\\sigma_{Q_{i,m}}}\n",
    "                    \\right)\n",
    "                    +\n",
    "                    \\left(\n",
    "                        \\frac{q_{i+j}-\\mu_{Q_{i,m}}}{\\sigma_{Q_{i,m}}}\n",
    "                    \\right)^2\n",
    "                \\right]\n",
    "        }\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\sqrt{\n",
    "            \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                \\left(\n",
    "                    \\frac{t_{i+j}-M_{T_{i,m}}}{\\Sigma_{T_{i,m}}}\n",
    "                \\right)^2\n",
    "                -\n",
    "            \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                2\n",
    "                \\left(\n",
    "                    \\frac{t_{i+j}-M_{T_{i,m}}}{\\Sigma_{T_{i,m}}}\n",
    "                \\right)\n",
    "                \\left(\n",
    "                    \\frac{q_j-\\mu_{Q_{i,m}}}{\\sigma_{Q_{i,m}}}\n",
    "                \\right)\n",
    "                +\n",
    "            \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                \\left(\n",
    "                    \\frac{q_{i+j}-\\mu_{Q_{i,m}}}{\\sigma_{Q_{i,m}}}\n",
    "                \\right)^2\n",
    "        }\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\sqrt{\n",
    "            m\n",
    "            -\n",
    "            \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                2\n",
    "                \\left(\n",
    "                    \\frac{t_{i+j}-M_{T_{i,m}}}{\\Sigma_{T_{i,m}}}\n",
    "                \\right)\n",
    "                \\left(\n",
    "                    \\frac{q_{i+j}-\\mu_{Q_{i,m}}}{\\sigma_{Q_{i,m}}}\n",
    "                \\right)\n",
    "            +\n",
    "            m\n",
    "        }\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\sqrt{\n",
    "            2m\n",
    "            -\n",
    "            2\n",
    "            \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                \\left(\n",
    "                    \\frac{t_{i+j}-M_{T_{i,m}}}{\\Sigma_{T_{i,m}}}\n",
    "                \\right)\n",
    "                \\left(\n",
    "                    \\frac{q_{i+j}-\\mu_{Q_m}}{\\sigma_{Q_{i,m}}}\n",
    "                \\right)\n",
    "        }\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\sqrt{\n",
    "            2m\n",
    "            \\left[\n",
    "                1\n",
    "                -\n",
    "                \\frac{1}{m}\n",
    "                \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                    \\left(\n",
    "                        \\frac{t_{i+j}-M_{T_{i,m}}}{\\Sigma_{T_{i,m}}}\n",
    "                    \\right)\n",
    "                    \\left(\n",
    "                        \\frac{q_{i+j}-\\mu_{Q_{i,m}}}{\\sigma_{Q_{i,m}}}\n",
    "                    \\right)\n",
    "            \\right]\n",
    "        }\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\sqrt{\n",
    "            2m\n",
    "            \\left[\n",
    "                1\n",
    "                -\n",
    "                \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                    \\frac{\n",
    "                        \\left(\n",
    "                            t_{i+j}-M_{T_{i,m}}\n",
    "                        \\right)\n",
    "                        \\left(\n",
    "                            q_{i+j}-\\mu_{Q_{i,m}}\n",
    "                        \\right)\n",
    "                    }{\n",
    "                        m \\sigma_{Q_{i,m}} \\Sigma_{T_{i,m}}\n",
    "                    }\n",
    "            \\right]\n",
    "        }\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\sqrt{\n",
    "            2m\n",
    "            \\left[\n",
    "                1\n",
    "                -\n",
    "                \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                    \\frac{\n",
    "                        t_{i+j}q_j\n",
    "                        -t_{i+j}\\mu_{Q_{i,m}}\n",
    "                        -M_{T_{i,m}}q_{i+j}\n",
    "                        +M_{T_{i,m}}\\mu_{Q_{i+m}}\n",
    "                    }{\n",
    "                        m \\sigma_{Q_{i+m}} \\Sigma_{T_{i,m}}\n",
    "                    }\n",
    "            \\right]\n",
    "        }\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\sqrt{\n",
    "            2m\n",
    "            \\left[\n",
    "                1\n",
    "                -\n",
    "                \\frac{\n",
    "                    \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                        q_{i+j}t_{i+j}\n",
    "                    -\n",
    "                    \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                        t_{i+j}\\mu_{Q_{i,m}}\n",
    "                    -\n",
    "                    \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                        \\left(\n",
    "                            M_{T_{i,m}}q_{i+j}\n",
    "                            -M_{T_{i,m}}{\\mu_{Q_{i,m}}}\n",
    "                        \\right)\n",
    "                }{\n",
    "                    m \\sigma_{Q_{i,m}} \\Sigma_{T_{i,m}}\n",
    "                }\n",
    "            \\right]\n",
    "        }\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\sqrt{\n",
    "            2m\n",
    "            \\left[\n",
    "                1\n",
    "                -\n",
    "                \\frac{\n",
    "                    Q_{i,m}\\cdot{T_{i,m}}\n",
    "                    -\n",
    "                    \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                        t_{i+j}\\mu_{Q_{i,m}}\n",
    "                    -\n",
    "                    M_{T_{i,m}}\n",
    "                    \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                        \\left(\n",
    "                            q_{i+j}-{\\mu_{Q_{i,m}}}\n",
    "                        \\right)\n",
    "                }{\n",
    "                    m \\sigma_{Q_{i,m}} \\Sigma_{T_{i,m}}\n",
    "                }\n",
    "            \\right]\n",
    "        }\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\sqrt{\n",
    "            2m\n",
    "            \\left[\n",
    "                1\n",
    "                -\n",
    "                \\frac{\n",
    "                    Q_{i,m}\\cdot{T_{i,m}}\n",
    "                    -\n",
    "                    \\mu_{Q_{i,m}}\n",
    "                    \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                        t_{i+j}\n",
    "                    -\n",
    "                    0\n",
    "                }{\n",
    "                    m \\sigma_{Q_{i,m}} \\Sigma_{T_{i,m}}\n",
    "                }\n",
    "            \\right]\n",
    "        }\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\sqrt{\n",
    "            2m\n",
    "            \\left[\n",
    "                1\n",
    "                -\n",
    "                \\frac{\n",
    "                    Q_{i,m}\\cdot{T_{i,m}}\n",
    "                    -\n",
    "                    \\mu_{Q_{i,m}}\n",
    "                    \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                        t_{i+j}\n",
    "                }{\n",
    "                    m \\sigma_{Q_{i,m}} \\Sigma_{T_{i,m}}\n",
    "                }\n",
    "            \\right]\n",
    "        }\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\sqrt{\n",
    "            2m\n",
    "            \\left[\n",
    "                1\n",
    "                -\n",
    "                \\frac{\n",
    "                    Q_{i,m}\\cdot{T_{i,m}}\n",
    "                    -\n",
    "                    \\mu_{Q{i,m}}m\n",
    "                    \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                        \\frac{t_{i+j}}{m}\n",
    "                }{\n",
    "                    m \\sigma_{Q_{i,m}} \\Sigma_{T_{i,m}}\n",
    "                }\n",
    "            \\right]\n",
    "        }\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\sqrt{\n",
    "            2m\n",
    "            \\left[\n",
    "                1\n",
    "                -\n",
    "                \\frac{\n",
    "                    Q_{i,m}\\cdot{T_{i,m}}\n",
    "                    -\n",
    "                    m\\mu_{Q_{i,m}}M_{T_{i,m}}\n",
    "                }{\n",
    "                    m \\sigma_{Q_{i,m}} \\Sigma_{T_{i,m}}\n",
    "                }\n",
    "            \\right]\n",
    "        }\n",
    "    \\\\        \n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Computing the  Z-Normalized Euclidean Distance from the Pearson Correlation\n",
    "\n",
    "Based on the fact that the Pearson Correlation, $\\rho$, can be written as (see Equation 4 in [this paper](https://www.cs.unm.edu/~mueen/Projects/JOCOR/joinICDM.pdf) or Equation 3 in [this paper](https://arxiv.org/pdf/1601.02213.pdf)):\n",
    "\n",
    "\\begin{align}\n",
    "    \\rho(Q_{i,m}, T_{i,m}) ={}& \\frac{E\n",
    "        \\left[\n",
    "            \\left(\n",
    "                Q_{i,m}-\\mu_{Q_{i,m}}\n",
    "            \\right)\n",
    "            \\left(\n",
    "                T_{i,m}-M_{T_{i,m}}\n",
    "            \\right)\n",
    "        \\right]\n",
    "    }{\\sigma_{Q_{i,m}}\\Sigma_{T_{i,m}}}\n",
    "    \\\\\n",
    "    ={}& \n",
    "        \\frac{\n",
    "            \\langle\n",
    "            \\left(\n",
    "                Q_{i,m}-\\mu_{Q_{i,m}}\n",
    "            \\right)\n",
    "            ,\n",
    "            \\left(\n",
    "                T_{i,m}-M_{T_{i,m}}\n",
    "            \\right)\n",
    "            \\rangle\n",
    "        }{\\sigma_{Q_{i,m}}\\Sigma_{T_{i,m}}}\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\frac{1}{m}\n",
    "        \\sum \\limits _{0 \\leq j \\lt m}\n",
    "            \\frac{\n",
    "                \\left(\n",
    "                    q_{i+j}-\\mu_{Q_{i,m}}\n",
    "                \\right)\n",
    "                \\left(\n",
    "                    t_{i+j}-M_{T_{i,m}}\n",
    "                \\right)\n",
    "            }{\\sigma_{Q_{i,m}}\\Sigma_{T_{i,m}}}\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\frac{1}{m}\n",
    "        \\sum \\limits _{0 \\leq j \\lt m}\n",
    "            \\left(\n",
    "                \\frac{\n",
    "                    q_{i+j}-\\mu_{Q_{i,m}}\n",
    "                }{\\sigma_{Q_{i,m}}}\n",
    "            \\right)\n",
    "            \\left(\n",
    "                \\frac{    \n",
    "                    t_{i+j}-M_{T_{i,m}}\n",
    "                }{\\Sigma_{T_{i,m}}}\n",
    "            \\right)\n",
    "    \\\\\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similar to above, the Z-normalized Euclidean distance can be computed from $\\rho$ following:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align}\n",
    "    D(Q_{i,m}, T_{i,m}) ={}&\n",
    "        \\sqrt{\n",
    "            \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                \\left(\n",
    "                    \\frac{t_{i+j}-M_{T_{i,m}}}{\\Sigma_{T_{i,m}}}\n",
    "                    - \n",
    "                    \\frac{q_{i+j}-\\mu_{Q_{i,m}}}{\\sigma_{Q_{i,m}}}\n",
    "                \\right)^2\n",
    "        }\n",
    "        \\\\\n",
    "    \\vdots\n",
    "        \\\\\n",
    "    ={}&\n",
    "        \\sqrt{\n",
    "            2m\n",
    "            \\left[\n",
    "                1\n",
    "                -\n",
    "                \\frac{1}{m}\n",
    "                \\sum \\limits _{0 \\leq {j} \\lt m}\n",
    "                    \\left(\n",
    "                        \\frac{t_{i+j}-M_{T_{i,m}}}{\\Sigma_{T_{i,m}}}\n",
    "                    \\right)\n",
    "                    \\left(\n",
    "                        \\frac{q_{i+j}-\\mu_{Q_{i,m}}}{\\sigma_{Q_{i,m}}}\n",
    "                    \\right)\n",
    "            \\right]\n",
    "        }\n",
    "        \\\\\n",
    "    ={}&\n",
    "        \\sqrt{\n",
    "            2m\n",
    "            \\left[\n",
    "                1\n",
    "                -\n",
    "                \\rho(Q_{i,m},T_{i,m})\n",
    "            \\right]\n",
    "        }\n",
    "        \\\\\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thus, by employing the most efficient way to compute $\\rho(Q_{i,m},T_{i,m})$, then we'd also have an efficient way to directly compute $D(Q_{i,m},T_{i,m})$. Recall that:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align}\n",
    "    \\rho(Q_{i,m},T_{i,m}) = \\frac{cov(Q_{i,m},T_{i,m})}{\\sigma_{Q_{i,m}}\\Sigma_{T_{i,m}}}\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thus, it follows that finding the most efficient way to compute the covariance matrix, $cov(Q_{i,m},T_{i,m})$ would result in the most efficient way to compute the distance. Also, remember that we would like to traverse our distance matrix along each diagonal rather than along each row/column."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Covariance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that the covariance, $cov(Q_{i,m},T_{i,m})$, can be written as:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align}\n",
    "    cov(Q_{i,m},T_{i,m}) ={}& E\n",
    "        \\left[\n",
    "            \\left(\n",
    "                Q-\\mu_{Q_{i,m}}\n",
    "            \\right)\n",
    "            \\left(\n",
    "                T_{i,m}-M_{T_{i,m}}\n",
    "            \\right)\n",
    "        \\right]\n",
    "    \\\\\n",
    "    ={}& \n",
    "        \\langle\n",
    "            \\left(\n",
    "                Q-\\mu_{Q_{i,m}}\n",
    "            \\right)\n",
    "            ,\n",
    "            \\left(\n",
    "                T_{i,m}-M_{T_{i,m}}\n",
    "            \\right)\n",
    "        \\rangle\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\frac{1}{m}\n",
    "        \\sum \\limits _{0 \\leq j \\lt m}\n",
    "            \\left(\n",
    "                q_{i+j}-\\mu_{Q_{i,m}}\n",
    "            \\right)\n",
    "            \\left(\n",
    "                t_{i+j}-M_{T_{i,m}}\n",
    "            \\right)\n",
    "    \\\\\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that we've explicitly called out the fact that the means, $\\mu_{Q_{{i,m}}}$ and $M_{T_{i,m}}$, are computed with the subsequences of length $m$. Additionally, according to Welford, we can express these means with respect to the means of the same subsequences that have their last elements removed (i.e., $\\mu_{Q_{i,m-1}}$ and $M_{T_{i,m-1}}$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align}\n",
    "    cov(Q_{i,m},T_{i,m}) \n",
    "    ={}&\n",
    "        \\frac{1}{m}\n",
    "        \\sum \\limits _{0 \\leq j \\lt m}\n",
    "            \\left(\n",
    "                q_{i+j}-\\mu_{Q_{i,m}}\n",
    "            \\right)\n",
    "            \\left(\n",
    "                t_{i+j}-M_{T_{i,m}}\n",
    "            \\right)\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\frac{\n",
    "            S(Q_{i,m-1}, T_{i,m-1})\n",
    "            +\n",
    "            \\left(\n",
    "                \\frac{m-1}{m}\n",
    "            \\right)        \n",
    "            \\left(\n",
    "                q_{i+m-1} - \\mu_{Q_{i,m-1}}\n",
    "            \\right)\n",
    "            \\left(\n",
    "                t_{i+m-1} - M_{T_{i,m-1}}\n",
    "            \\right)\n",
    "        }{m}\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\frac{\n",
    "            \\frac{m-1}{m-1}S(Q_{i,m-1}, T_{i,m-1})\n",
    "            +\n",
    "            \\left(\n",
    "                \\frac{m-1}{m}\n",
    "            \\right)        \n",
    "            \\left(\n",
    "                q_{i+m-1} - \\mu_{Q_{i,m-1}}\n",
    "            \\right)\n",
    "            \\left(\n",
    "                t_{i+m-1} - M_{T_{i,m-1}}\n",
    "            \\right)\n",
    "        }{m}\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\frac{\n",
    "            cov(Q_{i,m-1},T_{i,m-1}) (m-1)\n",
    "            +\n",
    "            \\left(\n",
    "                \\frac{m-1}{m}\n",
    "            \\right)        \n",
    "            \\left(\n",
    "                q_{i+m-1} - \\mu_{Q_{i,m-1}}\n",
    "            \\right)\n",
    "            \\left(\n",
    "                t_{i+m-1} - M_{T_{i,m-1}}\n",
    "            \\right)\n",
    "        }{m}\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\frac{m-1}{m} \n",
    "        \\left[\n",
    "            cov(Q_{i,m-1},T_{i,m-1})\n",
    "            +\n",
    "            \\frac{\n",
    "                \\left(\n",
    "                    q_{i+m-1} - \\mu_{Q_{i,m-1}}\n",
    "                \\right)\n",
    "                \\left(\n",
    "                    t_{i+m-1} - M_{T_{i,m-1}}\n",
    "                \\right)\n",
    "            }{m}\n",
    "        \\right]\n",
    "    \\\\\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly, $cov(Q_{i-1,m},T_{i-1,m})$ can also be expressed with respect to $cov(Q_{i,m-1},T_{i,m-1})$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align}\n",
    "    cov(Q_{i-1,m},T_{i-1,m}) \n",
    "    ={}&\n",
    "        \\frac{1}{m}\n",
    "        \\sum \\limits _{0 \\leq j \\lt m}\n",
    "            \\left(\n",
    "                q_{i+j-1}-\\mu_{Q_{i-1,m}}\n",
    "            \\right)\n",
    "            \\left(\n",
    "                t_{i+j-1}-M_{T_{i-1,m}}\n",
    "            \\right)\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\frac{\n",
    "            S(Q_{i,m-1},T_{i,m-1})\n",
    "            +\n",
    "            \\frac{m-1}{m}\n",
    "            \\left(\n",
    "                q_{i-1} \n",
    "                - \n",
    "                \\mu_{Q_{i,m-1}} \n",
    "            \\right)\n",
    "            \\left(\n",
    "                t_{i-1}\n",
    "                -\n",
    "                M_{T_{i,m-1}} \n",
    "            \\right)\n",
    "        }{m}\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\frac{\n",
    "            \\frac{m-1}{m-1}S(Q_{i,m-1},T_{i,m-1})\n",
    "            +\n",
    "            \\frac{m-1}{m}\n",
    "            \\left(\n",
    "                q_{i-1} \n",
    "                - \n",
    "                \\mu_{Q_{i,m-1}} \n",
    "            \\right)\n",
    "            \\left(\n",
    "                t_{i-1}\n",
    "                -\n",
    "                M_{T_{i,m-1}} \n",
    "            \\right)\n",
    "        }{m}\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\frac{\n",
    "            cov(Q_{i,m-1},T_{i,m-1}) (m-1)\n",
    "            +\n",
    "            \\left(\n",
    "                \\frac{m-1}{m}\n",
    "            \\right)        \n",
    "            \\left(\n",
    "                q_{i-1} \n",
    "                - \n",
    "                \\mu_{Q_{i,m-1}} \n",
    "            \\right)\n",
    "            \\left(\n",
    "                t_{i-1}\n",
    "                -\n",
    "                M_{T_{i,m-1}} \n",
    "            \\right)\n",
    "        }{m}\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\frac{m-1}{m} \n",
    "        \\left[\n",
    "            cov(Q_{i,m-1},T_{i,m-1})\n",
    "            +\n",
    "            \\frac{\n",
    "                \\left(\n",
    "                    q_{i-1} \n",
    "                    - \n",
    "                    \\mu_{Q_{i,m-1}} \n",
    "                \\right)\n",
    "                \\left(\n",
    "                    t_{i-1}\n",
    "                    -\n",
    "                    M_{T_{i,m-1}} \n",
    "                \\right)\n",
    "            }{m}\n",
    "        \\right]\n",
    "    \\\\\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we can rearrange this and express $cov(Q_{i,m-1},T_{i,m-1})$ as a function of $cov(Q_{i-1,m},T_{i-1,m})$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align}\n",
    "    cov(Q_{i-1,m},T_{i-1,m})\n",
    "    ={}&\n",
    "        \\frac{m-1}{m} \n",
    "        \\left[\n",
    "            cov(Q_{i,m-1},T_{i,m-1})\n",
    "            +\n",
    "            \\frac{\n",
    "                \\left(\n",
    "                    q_{i-1} \n",
    "                    - \n",
    "                    \\mu_{Q_{i,m-1}} \n",
    "                \\right)\n",
    "                \\left(\n",
    "                    t_{i-1}\n",
    "                    -\n",
    "                    M_{T_{i,m-1}} \n",
    "                \\right)\n",
    "            }{m}\n",
    "        \\right]\n",
    "    \\\\\n",
    "    \\frac{m}{m-1} \n",
    "    cov(Q_{i-1,m},T_{i-1,m})\n",
    "    -\n",
    "    \\frac{\n",
    "        \\left(\n",
    "            q_{i-1} \n",
    "            - \n",
    "            \\mu_{Q_{i,m-1}} \n",
    "        \\right)\n",
    "        \\left(\n",
    "            t_{i-1}\n",
    "            -\n",
    "            M_{T_{i,m-1}} \n",
    "        \\right)\n",
    "    }{m}\n",
    "    ={}&\n",
    "        cov(Q_{i,m-1},T_{i,m-1})\n",
    "    \\\\\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And we can then substitute this representation of $cov(Q_{i,m-1},T_{i,m-1})$ into our $cov(Q_{i,m},T_{i,m})$ equation from above and get:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align}\n",
    "    cov(Q_{i,m},T_{i,m})\n",
    "    ={}&\n",
    "        \\frac{m-1}{m} \n",
    "        \\left[\n",
    "            cov(Q_{i,m-1},T_{i,m-1})\n",
    "            +\n",
    "            \\frac{\n",
    "                \\left(\n",
    "                    q_{i+m-1} - \\mu_{Q_{i,m-1}}\n",
    "                \\right)\n",
    "                \\left(\n",
    "                    t_{i+m-1} - M_{T_{i,m-1}}\n",
    "                \\right)\n",
    "            }{m}\n",
    "        \\right]\n",
    "    \\\\\n",
    "    ={}&\n",
    "        \\frac{m-1}{m} \n",
    "        \\left[\n",
    "            \\frac{m}{m-1}\n",
    "            cov(Q_{i-1,m},T_{i-1,m})\n",
    "            -\n",
    "            \\frac{\n",
    "                \\left(\n",
    "                    q_{i-1} \n",
    "                    - \n",
    "                    \\mu_{Q_{i,m-1}} \n",
    "                \\right)\n",
    "                \\left(\n",
    "                    t_{i-1}\n",
    "                    -\n",
    "                    M_{T_{i,m-1}} \n",
    "                \\right)\n",
    "            }{m}\n",
    "            +\n",
    "            \\frac{\n",
    "                \\left(\n",
    "                    q_{i+m-1} - \\mu_{Q_{i,m-1}}\n",
    "                \\right)\n",
    "                \\left(\n",
    "                    t_{i+m-1} - M_{T_{i,m-1}}\n",
    "                \\right)\n",
    "            }{m}\n",
    "        \\right]\n",
    "    \\\\\n",
    "    ={}&\n",
    "        cov(Q_{i-1,m},T_{i-1,m})\n",
    "        +\n",
    "        \\frac{m-1}{m^2}\n",
    "        \\left[\n",
    "            \\left(\n",
    "                q_{i+m-1} - \\mu_{Q_{i,m-1}}\n",
    "            \\right)\n",
    "            \\left(\n",
    "                t_{i+m-1} - M_{T_{i,m-1}}\n",
    "            \\right)\n",
    "            -\n",
    "            \\left(\n",
    "                q_{i-1} \n",
    "                - \n",
    "                \\mu_{Q_{i,m-1}} \n",
    "            \\right)\n",
    "            \\left(\n",
    "                t_{i-1}\n",
    "                -\n",
    "                M_{T_{i,m-1}} \n",
    "            \\right)\n",
    "        \\right]\n",
    "    \\\\\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Pearson Correlation\n",
    "\n",
    "\\begin{align}\n",
    "    \\rho(Q_{i,m},T_{i,m}) \n",
    "    &{}= \n",
    "        \\frac{cov(Q_{i,m},T_{i,m})}{\\sigma_{Q_{i,m}}\\Sigma_{T_{i,m}}}\n",
    "    \\\\\n",
    "    &{}=\n",
    "        \\frac{\n",
    "            cov(Q_{i-1,m},T_{i-1,m})\n",
    "        +\n",
    "        \\frac{m-1}{m^2}\n",
    "        \\left[\n",
    "            \\left(\n",
    "                q_{i+m-1} - \\mu_{Q_{i,m-1}}\n",
    "            \\right)\n",
    "            \\left(\n",
    "                t_{i+m-1} - M_{T_{i,m-1}}\n",
    "            \\right)\n",
    "            -\n",
    "            \\left(\n",
    "                q_{i-1} \n",
    "                - \n",
    "                \\mu_{Q_{i,m-1}} \n",
    "            \\right)\n",
    "            \\left(\n",
    "                t_{i-1}\n",
    "                -\n",
    "                M_{T_{i,m-1}} \n",
    "            \\right)\n",
    "        \\right]\n",
    "        }{\\sigma_{Q_{i,m}}\\Sigma_{T_{i,m}}}\n",
    "    \\\\\n",
    "\\end{align}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Z-Normalized Distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
